package org.example.l0;

import org.example.l2.CharHelper;
import org.junit.jupiter.api.Test;

import java.util.stream.IntStream;

public class graph {

    @Test
    void aa2() {
//        char[][] from = CharHelper.from("[[\"1\",\"1\",\"1\",\"1\",\"0\"],[\"1\",\"1\",\"0\",\"1\",\"0\"],[\"1\",\"1\",\"0\",\"0\",\"0\"]]\n");
        char[][] from = CharHelper.from("[[\"1\",\"1\",\"0\",\"0\",\"0\"],[\"1\",\"1\",\"0\",\"0\",\"0\"],[\"0\",\"0\",\"1\",\"0\",\"0\"],[\"0\",\"0\",\"0\",\"1\",\"1\"]]\n");
        int i = numIslands(from);
        System.out.println(i);
    }

    int[] p;
    int res;

    int find(int i) {
        if (p[i] == i) {
            return p[i];
        }
        return p[i] = find(p[i]);
    }

    void union(int i,
               int j) {
        if (find(i) == find(j)) {
            return; //避免重复合并操作
        }
        p[find(i)] = p[find(j)];
        res--;
    }

    public int numIslands(char[][] grid) {
        int len1 = grid.length;
        int len2 = grid[0].length;
        p = IntStream.range(0, len1 * len2).toArray();
        res = 0;
        for (char[] chars : grid) {
            for (char aChar : chars) {
                if (aChar == '1') {
                    res++;
                }
            }
        }
        for (int i = 0; i < len1; i++) {
            for (int j = 0; j < len2; j++) {
                int idx = i * len2 + j;
                if (grid[i][j] == '0') {
                    continue;
                }
                if (i + 1 < len1 && grid[i + 1][j] == '1') { //合并岛屿
                    union(idx, idx + len2);
                }
                if (j + 1 < len2 && grid[i][j + 1] == '1') {
                    union(idx, idx + 1);
                }
            }
        }
        return res;
    }
}
